|
Efficient cake-cutting is a problem in economics and computer science. It involves a ''heterogenous'' resource, such as a cake with different toppings or a land with different coverings, that is assumed to be ''divisible'' - it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible, etc. The division should be ''economically efficient''. Several definitions to efficiency are described below. Most often, efficiency is studied in connection with fairness, and the goal is to find a division which satisfies both efficiency and fairness criteria. == Assumptions == There is a cake ''C'', which is usually assumed to be either a finite 1-dimensional segment, a 2-dimensional polygon or a finite subset of the multidimensional Euclidean plane ''R''''d''. There are ''n'' people. Each person ''i'' has a subjective value function ''Vi'' which maps subsets of ''C'' to numbers. ''C'' has to be divided to ''n'' disjoint subsets, such that each person receives a disjoint subset. The piece allocated to person ''i'' is called ''Pi'', and . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Efficient cake-cutting」の詳細全文を読む スポンサード リンク
|